\documentclass{beamer}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[latin1]{inputenc}
\usepackage{url}
\usepackage{beamerthemesplit}

%\usepackage{beamerthemeshadow}
%\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
%\usepackage{amsmath,amssymb}
%\usepackage[latin1]{inputenc}
%\usepackage{colortbl}
%\usepackage[english]{babel}
%\usepackage{amsfonts}
%\usepackage{mathrsfs}
%\usepackage{wrapfig}
%\usepackage[twlrm]{rawfonts} %xfig
%\usepackage{graphics}
%\usepackage{psfig}
\usepackage{subfig} % este é para fazer sub figuras
\usepackage{graphicx}
%\usepackage{times}
%\usepackage[all]{xy}
%\usepackage{slideformat}
\usepackage{listings}

\title[]{Análise Semântica {\it Tradutores}}
\author[]{Universidade de Brasília\\Instituto de Ciências Exatas \\Departamento de Ciência da Computação\\Gabriel Heleno Gonçalves da Silva\\Leonardo Melo\\Igor Rafael de Sousa}
\date{Brasília, 17 de Janeiro de 2012}

\begin{document}
\begin{frame}

\begin{columns}

\column {0.2\textwidth}
%\includegraphics[scale=0.5]{Logo_UnB.jpg}

\column {0.4\textwidth}
\begin{center}
\scriptsize {Universidade de Brasília\\Departamento de Ciência da Computação}
\end{center}

\end{columns}

\titlepage
\end{frame}


%\AtBeginSection[]
%{
%\begin{frame}
%\frametitle{Sumário}
%\tableofcontents[currentsection,currentsubsection]
%\end{frame}
%}



\section{Tópicos}

\frame{
	\frametitle{Ambientes em Tempo de Execução}
	\begin{itemize}
		\item<1-> Temas da Linguagem-Fonte;
		\item<1-> Organização de Memória;
		\item<1-> Estratégias para Alocação de Memória;
		\item<1-> Acesso aos Nomes não Locais;
		\item<1-> Transmissão de Parâmetros;
		\item<1-> Tabelas de Símbolos;
%		\item<1-> Facilidades de Linguagem para a Alocação de Memória;
%		\item<1-> Técnicas de Alocação de Memória;
	\end{itemize}
}

\section{Temas da Linguagem-Fonte}

\subsection{Procedimentos}

\frame{
	\begin{itemize}
		\item<1-> Declaração que, na sua forma mais simples, associa um identificador a um enunciado;
		\item<1-> Identificador = nome do procedimento;
		\item<1-> Enunciado = corpo do procedimento;
		\begin{tabbing}
			{\bf procedure} \= readarray; \\
			\> {\bf var} \= i : {\bf integer}; \\
			\> {\bf begin} \\
			\> \> {\bf for} i := 1 {\bf to} 9 {\bf do read } (a[i]) \\
			\> {\bf end}
		\end{tabbing}
	\end{itemize}
}


\frame{
	\begin{itemize}
		\item<1-> A chamada de procedimento executa o corpo do nome do procedimento;
		\item<1-> Alguns identificadores são especiais e são chamados de {\it parâmetros formais} do procedimento;
		\item<1-> Argumentos são {\it parâmetros atuais} que podem ser transmitidos ao procedimento chamado;
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Exemplo:
		\begin{tabbing}
			{\bf program} \= sort (input, output); \\
			\> {\bf procedure} \= readarray; \\
			\> \> {\bf var} i : {\bf integer}; \\
			\> \> {\bf begin} \= \\
			\> \> \> {\bf for} i := 1 {\bf to} 9 {\bf do read } (a[i]) \\
			\> \> {\bf end} \\
			\> {\bf procedure} \= partition (y,z : integer) : integer; \\
			\> \> {\bf var} i, j, x, v : {\bf integer}; \\
			\> \> {\bf begin} \\
			\> \> {\bf end} \\
		\end{tabbing}
	\end{itemize}
}

\frame{
		\begin{tabbing}
			{\bf procedure} \= quicksort (m, n : integer); \\
			\> {\bf var} i : {\bf integer}; \\
			\> {\bf begin} \= \\
			\> \> {\bf if} (n $>$ m) {\bf then} \\
			\> \> {\bf begin} \= \\
			\> \> \> i := partition (m,n); \\
			\> \> \> quicksort (m,i-1); \\
			\> \> \> quicksort (i+1,n); \\
			\> \> {\bf end} \\
			\> {\bf end} \\
		\end{tabbing}
}

\frame{
		\begin{tabbing}
			{\bf begin} \= \\
			\> a[0] := -9999; a[10] := 9999; \\
			\> readarray; \\
			\> quicksort (1,9) \\
			{\bf end.} \\
		\end{tabbing}
}

\subsection{Árvores de Ativações}

\frame{
	\begin{itemize}
		\item<1-> Suposições sobre o fluxo de controle entre procedimentos durante a execução de um programa:
		\begin{enumerate}
			\item O controle flui sequencialmente;
			\item Cada execução de um procedimento começa no início do corpo e retorna o controle para o ponto imediatamente seguinte ao local de onde foi chamado;
		\end{enumerate}
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Ativação do procedimento;
		\item<1-> Tempo de vida;
		\begin{enumerate}
			\item Tempos de vida ou são não sobrepostos ou aninhados;
		\end{enumerate}
		\item<1-> Um procedimento é {\it recursivo} se uma nova aplicação puder começar antes que uma ativação anterior do mesmo procedimento tenha terminado;
		\begin{enumerate}
			\item Não precisa chamar diretamente;
			\item Pode ser utilizada uma {\it árvore de ativações};
		\end{enumerate}
		
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Em uma {\it árvore de ativações};
		\begin{enumerate}
			\item cada nó representa uma ativação de um procedimento,
			\item a raiz representa a ativação do programa principal,
			\item o nó para {\it a} é o pai do nó para {\it b} se e somente se o controle fluir da ativação de {\it a} para {\it b} e 				
			\item o nó para {\it a} está à esquerda do nó para {\it b} se e somente se o tempo de vida de {\it a} decorrer antes do tempo de vida de {\it b}.
		\end{enumerate}
		
	\end{itemize}
}

\subsection{Pilhas de Controle}

\frame{
	\begin{itemize}
		\item<1-> O fluxo de controle em um procedimento corresponde a uma travessia em profundidade da árvore de ativações:
		\item<1-> Obs.: colocar a árvore de ativações;
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Pode-se usar uma pilha de controle:
		\begin{enumerate}
			\item empilhar o nó quando a ativação se iniciar e
			\item remover o nó quando a mesma terminar.
		\end{enumerate}
		\item<1-> Nó n no topo da pilha de controle conterá os nós ao longo do percurso de n até a raiz.
	\end{itemize}
}


\subsection{O Escopo de uma Declaração}

\frame{
	\begin{itemize}
		\item<1-> Uma declaração numa linguagem é uma construção sintática que associa informações a um nome;
		\item<1-> Podem ser explícitas:
		\begin{enumerate}
			\item var i : integer;
		\end{enumerate}
		\item<1-> ou implícitas:
		\lstinputlisting[language=C,firstline=3, lastline=6]{idade.c}

	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Parte do programa a qual uma declaração se aplica é o {\it escopo da declaração};
		\item<1-> Ocorrência dentro do procedimento é dita {\it local};
		\item<1-> Caso contrário, {\it não-local};
		\item<1-> A distinção recai sobre qualquer construção sintática com declarações dentro de si;
		\begin{tabbing}
			{\bf procedure} \= readarray; \\
			\> {\bf var} i : {\bf integer}; \\
			\> {\bf begin} \= \\
			\> \> {\bf for} i := 1 {\bf to} 9 {\bf do read } (a[i]) \\
			\> {\bf end} 
		\end{tabbing}
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Em tempo de compilação, a tabela de símbolos pode ser usada para:
		\begin{enumerate}
			\item quando encontrada, é criada uma entrada;
			\item enquanto no escopo, sua entrada é retornada;
		\end{enumerate}
	\end{itemize}
}

\subsection{Amarrações de Nomes}

\frame{
	\begin{itemize}
		\item<1-> O nome poderá denotar {\it objeto de dados} diferentes;
		\item<1-> {\it Ambiente} se refere a uma função que mapeia um nome em uma localização de memória;
		\item<1-> {\it Estado} se refere a uma função que mapeia a localização de memória no valor guardado nela;
		\item<1-> nome $\rightarrow$ ambiente() $\rightarrow$ memória $\rightarrow$ estado() $\rightarrow$ valor
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Uma atribuição modifica o {\it estado} mas não o {\it ambiente}:
		\begin{enumerate}
			\item endereço de memória 100, associado a {\bf x}, com valor 0;
			\item {\bf x} = 3.14;
			\item {\bf x} ainda está associado ao endereço de memória 100, mas com valor 3.14.
		\end{enumerate}
	\end{itemize}
}

\frame{

		\begin{columns}[t]
			\begin{column}{6,5cm}
				\begin{itemize}
					\item<1-> NOÇÃO ESTÁTICA
					\begin{enumerate}
						\item definição de um procedimento
						\item declaração de um nome
						\item escopo de uma declaração
					\end{enumerate}
				\end{itemize}
			\end{column}
			\begin{column}{6cm}
				\begin{itemize}
					\item<1-> CONTRAPARTE DINÂMICA
					\begin{enumerate}
						\item ativação de um procedimento
						\item amarrações de um nome
						\item tempo de vida de uma amarração
					\end{enumerate}
				\end{itemize}
			\end{column}
		\end{columns}
}




\section{Organização da Memória}

\frame
{
 \begin{itemize}

 \item<1-> Em tempo de execução a memória abriga: O código-alvo gerado, objetos de dados e a contraparte da pilha de controle para controlar as ativações de procedimentos

 \item<1-> O tamanho do código gerado é estabelecido em tempo de compilação e assim o compilador pode colocá-lo numa área estaticamente determinada

 \item<1-> Os objetos de dados que assim permitirem são alocados estaticamente

 \item<1-> Uma área separada de memória, chamada de heap, guarda as outras informações

  \end{itemize}
}

\subsection{Regras de Aninhamento}

\frame
{
 \begin{itemize}

 \item<1-> As informações necessárias por uma única execução de um procedimento são gerenciadas utilizando-se um bloco contíguo de armazenamento chamado de registro de ativação

 \item<1-> Os registros de ativação são divididos em:

 \item<1-> Valores Temporários - Ex.: Resultado da avaliação de expressões

 \item<1-> Dados locais

 \item<1-> Estado da máquina - Ex.: Valores de contadores

 \item<1-> Elo de acesso opcional, que são dados locais obrigatórios em outros registros de ativação

 \item<1-> Elo de controle, que é o registro de ativação do chamador

 \item<1-> Campos para parâmetros

 \item<1-> Campo para o valor retornado

  \end{itemize}
}

\subsection{Gabarito Para os Dados Locais em Tempo de Compilação}
\frame
{
 \begin{itemize}

 \item<1-> A quantidade de memória necessitada por um nome é determinada pelo seu tipo

 \item<1-> O campo para os dados locais é estabelecido na medida que as declarações são examinadas em tempo de compilação

 \item<1-> Dados de tamanho variável ficam fora desse campo

 \item<1-> A partir do contador determinamos o endereço relativo de armazenamento para um objeto de dados local em relação a alguma posição

  \end{itemize}
}


\subsection{Endereçamento}

\frame
{
 \begin{itemize}

 \item<1-> A disposição da memória para os objetos de dados é fortemente influenciada pelas restrições de endereçamento da máquina-alvo

 \item<1-> Ex.: As instruções para adicionar inteiros podem esperar que os mesmos sejam alinhados, isto é, colocados em certas posições na memória, tal como num endereço divisível por 4

 \item<1-> Apesar de um array de 10 caracteres precisar somente de dez bytes para abrigá-los um compilador pode, no entanto, reservar doze bytes, deixando 2 bytes sem uso

 \item<1-> Esses bytes são chamados de bytes de preenchimento

  \end{itemize}
}




\section{Estratégias para a Alocação de Memória}

\subsection{Introdução}

\frame{
%	\begin{itemize}
%		\item<1->
		\begin{enumerate}
			\item A alocação de memória estática dispõe o armazenamento para todos os objetos de dados em tempo de compilação.
			\item A alocação de memória de pilha gerencia a memória em tempo de execução como uma pilha.
			\item A alocação de memória heap reserva e libera as áreas de armazenamento na medida do necessitado em tempo de execução.
		\end{enumerate}
%	\end{itemize}
}

\subsection{Alocação de Memória Estática}

\frame{
	\begin{itemize}
		\item<1-> Os nomes são amarrados às localizações de memória a medida que o programa é compilado;
		\item<1-> As amarrações não se modificam em tempo de execução;
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> O compilador determina a quantidade de memória a ser reservada a partir do tipo do nome:
		\begin{enumerate}
			\item char: 1 byte; short int: 2 bytes; int: 4 bytes; 
			\item O endereço consiste no deslocamento de uma das extremidades do registro de ativação do procedimento;
			\item Compilador decide, eventualmente, onde os registros de ativação irão ficar:
			\begin{description}
				\item{-} posição relativa ao código-alvo do programa,
				\item{-} posições relativas entre si.
			\end{description}
			\item Em tempo de compilação podemos, por conseguinte, preencher os endereços aos quais o código-alvo poderá encontrar os dados sobre os quais opera e,
			\item conhecer os endereços aos quais as informações devem ser salvas quando ocorre uma chamada de procedimento.
		\end{enumerate}
	\end{itemize}
}



\frame{
	\begin{itemize}
		\item<1-> Limitações da memória estática:
		\begin{enumerate}
			\item tamanho dos objetos de dados e as restrições de suas posições na memória precisam ser conhecidas em tempo de compilação,
			\item os procedimentos recursivos estão restringidos e
			\item as estruturas de dados não podem ser criadas dinamicamente.
		\end{enumerate}
	\end{itemize}
}

\subsection{Alocação de Memória de Pilha}

\frame{
	\begin{itemize}
		\item<1-> Está baseada na ideia de uma pilha de controle:
		\begin{enumerate}
			\item Os registros de ativação são empilhados e desempilhados à medida que as ativações começam e terminam, respectivamente,
			\item O armazenamento para os objetos de dados locais está contido no registro de ativação de cada chamada do procedimento;
			\item Ao desempilhar o registro de ativação, os valores são perdidos.
		\end{enumerate}
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Tamanho dos registros de ativação conhecidos em tempo de compilação;
		\item<1-> Ou seja, se um procedimento {\it p} possui um registro de ativação de tamanho {\it x}, 
		\item<1-> então {\it topo} é incrementado de {\it x} exatamente antes do código alvo de {\it p} ser executado e
		\item<1-> quando o controle retorna de {\it p}, {\it topo} é decrementado de {\it x}.
	\end{itemize}
}

\frame{
	\begin{columns}[t]
		\begin{column}{6,5cm}
			\begin{center}
				\begin{tabular}{|c|}
					\hline
					s  \\
					a : array  \\
					\hline
					\hline
					s  \\
					a : array \\
					\hline
					r \\
					i : integer \\
					\hline
					\hline
					s  \\
					a : array \\
					\hline
					q(1:9) \\
					i : integer \\
					\hline
					\hline
				\end{tabular}
			\end{center}
		\end{column}
		\begin{column}{6,5cm}
			\begin{center}
				\begin{tabular}{|c|}
					\hline
					s  \\
					a : array \\
					\hline
					q(1:9) \\
					i : integer \\
					\hline
					q(1,3) \\
					i : integer \\
					\hline
					\hline
				\end{tabular}
			\end{center}
		\end{column}
	\end{columns}
}


\frame{
	\begin{itemize}
		\item<1-> Sequência de chamada:
		\begin{enumerate}
			\item<1-> O chamador avalia seus parâmetros atuais;
			\item<1-> O chamador armazena um endereço de retorno e o valor antigo ap\underline{ }topo no registro de ativação do procedimento chamado. O chamador então incrementa ap\underline{ }topo para a posição de responsabilidade do chamado;
			\item<1-> O procedimento chamado salva os valores dos registros e outras informações de estado;
			\item<1-> O procedimento chamado inicializa seus dados locais e começa a execução.
		\end{enumerate}
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Uma possível sequência de retorno é:
		\begin{enumerate}
			\item<1-> O procedimento chamado coloca um valor de retorno em seguida ao registro de ativação do chamador;
			\item<1-> O procedimento chamado restaura ap\underline{ }topo e outros registradores e desvia para um endereço de retorno no código do procedimento chamador;
			\item<1-> Apesar de ap\underline{ }topo ter sido decrementado, o procedimento chamador pode copiar o valor retornado em seu próprio registro de ativação e usá-lo para avaliar uma expressão.
		\end{enumerate}
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Podemos observar que:
		\begin{enumerate}
			\item<1-> O número de argumentos do procedimento chamado depende da chamada;
			\item<1-> Em tempo de compilação, o código-alvo do chamador conhece o número de argumentos que está fornecendo ao procedimento chamado.
			\item<1-> Porém, o código-alvo do procedimendo chamado precisa ser preparado para tratar outras chamadas igualmente e espera ser chamado para examinar o campo de parâmetros;
		\end{enumerate}
		\item<1-> As informações descrevendo os parâmetros precisam ser contíguas ao campo de estado, para que o procedimento chamado possa encontrá-las.
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Os dados de tamanho variável podem ser tratados:
		\begin{enumerate}
			\item<1-> Suponha que um procedimento {\it p} possua 3 {\it arrays} locais;
			\item<1-> O armazenamento para esses {\it arrays} não faz parte do registro de ativação;
			\item<1-> Os endereços relativos são conhecidos em tempo de compilação e o código-alvo pode ter acesso aos elementos do {\it array} através de ponteiros;
		\end{enumerate}
	\end{itemize}
}

\subsection{Referências Ocas}

\frame{
	\begin{itemize}
		\item<1-> Ocorre quando se referencia uma memória que já foi liberada.
		\lstinputlisting[language=C, firstline=12, lastline=23, basicstyle = \footnotesize]{ref_oca.c}
%		\lstinputlisting[language=C, firstline=25, lastline=27, basicstyle = \footnotesize]{ref_oca.c}
		\item<1-> Como a memória pode ser posteriormente reservada para um outro dado, erros misteriosos podem aparecer.
	\end{itemize}
}

\subsection{Alocação de Memória Heap}

\frame{
	\begin{itemize}
		\item<1-> A alocação de memória de pilha não pode ser usada se uma das seguintes situações for possível:
		\begin{enumerate}
			\item Os valores dos nomes locais precisarem ser retidos quando a ativação terminar;
			\item A ativação chamada sobreviver ao chamador.
		\end{enumerate}
%		\item<1-> 
	\end{itemize}
}


\frame{
	\begin{itemize}
		\item<1-> A alocação de memória {\it heap} fornece blocos de memória contígua, na medida do necessitado, para os registros de ativação ou outros objetos;
		\item<1-> A área de memória pode ser liberada em qualquer ordem;
		\item<1-> Ao longo do tempo, o {\it heap} irá se constituir de áreas alternativamente livres e em uso.
		\item<1-> A diferença entre {\it heap} e {\it pilha} é que no primeiro o registro para uma ativação do procedimento é retido ao término da mesma, enquanto na pilha não, podendo, assim, o registro seguir fisicamente para a nova ativação àquela inicial;
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Pode ser vantajoso manipular pequenos registros de ativação ou registros de tamanhos previsíveis:
		\begin{enumerate}
			\item Para cada tamanho específico de interesse, manter uma lista ligada de blocos livres daquele tamanho;
			\item Se possível, atender a uma requisição para um tamanho {\it s} com um bloco de tamanho {\it s'}, onde {\it s'} é o menor tamanho maior ou igual a {\it s};
			\item Quando o bloco for liberado, será retornado à lista ligada da qual é oriundo;
			\item Para grandes blocos de memória, usar o gerenciador de {\it heap}.
		\end{enumerate}
	\end{itemize}
}


\section{Acesso aos Nomes Não Locais}

\frame
{
 \begin{itemize}

 \item<1-> As estratégias de alocação de memória são adaptadas de forma a permitir o acesso aos nomes não locais

 \item<1-> As regras de escopo de uma linguagem determina o tratamento das referências aos nomes não locais

 \item<1-> A regra de escopo léxico ou estático determina a declaração que se aplica a um nome pelo exame isolado do texto do programa, tal como ocorre em Pascal e C

 \item<1-> A regra de escopo dinâmico determina a declaração aplicável a um nome em tempo de execução pela consideração das ativações correntes, essa regra é utilizada em Lisp, Apl e Snobol
  \end{itemize}
}


\subsection{Blocos}

\frame
{
 \begin{itemize}

 \item<1-> Bloco é um enunciado contendo suas próprias declarações de dados locais

 \item<1-> Uma característica dos blocos é a sua estrutura de aninhamento, os delimitadores marcam o início e o final do bloco

 \item<1-> Delimitadores asseguram que um bloco é independente ou está aninhado dentro de outro bloco. Isso impede que dois blocos $B_1$ e $B_2$ se sobreporem, de forma que o primeiro $B_1$ comece e em seguida $B_2$, mas que $B_1$ termine antes de $B_2$. Essa propriedade de aninhamento é algumas vezes referenciada como estrutura de bloco

 \item<1-> O escopo de uma declaração numa linguagem estruturada em blocos é dado pela regra do aninhamento mais interno
  \end{itemize}
}

\frame
{

 \begin{figure}

 	\includegraphics[width=0.8\textwidth]{Imag2.jpg}
 	\label{Imag2}
 \end{figure}
}


\subsection{Regras de Aninhamento}

\frame
{
 \begin{itemize}

 \item<1-> 1 - O escopo de uma declaração no bloco B inclui B

 \item<1-> 2 - Se um nome x não for declarado num bloco B, uma ocorrência de x em B estará no escopo de uma declaração x num bloco envolvente B' tal que

 \item<1-> i) B' possui uma declaração para x

 \item<1-> ii) B' é o bloco mais internamente aninhado envolvendo B, em relação a qualquer outro bloco que contenha uma declaração para x
  \end{itemize}
}

\subsection{Implementação da Estrutura de Blocos}

\frame
{
 \begin{itemize}

 \item<1-> A estrutura de blocos pode ser implementada usando-se uma alocação de memória de pilha. Uma vez que o escopo de uma declaração não se estende para fora do bloco para o qual aparece, o espaço para o nome declarado pode ser reservado quando o controle entra no bloco e liberado quando o deixa

 \item<1-> Essa visão trata os blocos como "procedimentos sem parâmetros"

 \item<1-> A chamada ocorre somente a partir do ponto exatamente antes do bloco e retornando somente para o ponto posterior

 \item<1-> Assim a memória necessária para a execução de determinado bloco, exceto a alocação por ponteiros, pode ser definida em tempo de compilação e assegurar que os as partes de um if-then-else ou os comandos dentro de um while sejam todos atingidos
  \end{itemize}
}


\subsection{Escopo Léxico sem Procedimentos Aninhados}

\frame
{
 \begin{itemize}

 \item<1-> Linguegens como C não permitem o aninhamento dos procedimentos tornando as regras de escopo estático mais simples

 \item<1-> O armazenamento para todos os nomes declarados fora de quaisquer procedimentos pode ser alocado estaticamente. A posição desse armazenamento é conhecida em tempo de compilação, e dessa forma, se um nome for não local ao corpo de um procedimento, usamos simplesmente o endereço determidado estaticamente
  \end{itemize}
}


\frame
{
 \begin{itemize}

 \item<1-> Com o escopo léxico e sem procedimentos aninhados, qualquer nome não local a um procedimento é não local a todos os procedimentos. Seu endereço estático pode ser usado em todos os procedimentos, independentemente de como sejam ativados

 \item<1-> Similarmente, se os procedimentos são retornados como resultado, os nomes não locais nos procedimentos retornados se referem à memória reservada estaticamente para os mesmos
  \end{itemize}
}

\subsection{Escopo Léxico com Procedimentos Aninhados}

\frame
{
 \begin{itemize}

 \item<1-> Uma ocorrência não local de um nome a num procedimento Pascal está no escopo da declaração de a mais internamente aninhada, envolvendo o procedimento no texto estático do programa

 \item<1-> A noção de profundidade do aninhamento de um procedimento se refere à distância entre o local onde o nome é declarado e o local no qual está sendo usado, adicionando 1 à profundidade de aninhamento à medida que nos encaminhamos de um procedimento envolvente para um procedimento envolvido
  \end{itemize}
}

\frame
{

 \begin{figure}

 	\includegraphics[width=0.8\textwidth]{Imag1.jpg}
 	\label{Imag1}
 \end{figure}
}


\frame
{
 \begin{itemize}
 \item<1-> No exemplo, o procedimento quicksort à linha 11 está à profundidade 2, enquanto que partition à linha 13 está à profundidade de aninhamento 3
\

\
 \item<1-> A cada ocorrência de um nome associamos a profundidade de aninhamento do procedimento no qual é declarado
  \end{itemize}
}

\section{Acesso aos Nomes Não Locais II}

\subsection{Elos de Acesso}

\frame
{
 \begin{itemize}

 \item<1-> Uma implementação direta do escopo léxico para procedimento aninhados é obtida adicionando-se um ponteiro, chamado de elo de acesso, a cada registro de ativação

 \item<1-> O elo de acesso para a ativação de sort está vazio, já que não há procedimento mais envolvente

 \item<1-> O elo de acesso de quicksort aponta para o registro de sort

 \item<1-> O elo de acesso no registro de ativação para partition aponta para o elo de acesso no registro de ativação mais recente de quicksort
  \end{itemize}
}


\subsection{Elos Entre Procedimentos e Nomes}
\frame
{
 \begin{itemize}

 \item<1-> Suponhamos que o procedimento p à profundidade de aninhamento $n_p$ se refira ao nome não local a com nível de aninhamento $n_a$ $\le$ $n_p$. O armazenamento de a pode ser encontrado como segue

 \item<1-> Quando o controle estiver em p, um registro de ativação para p está ao topo da pilha. Seguir $n_p$ - $n_a$ elos de acesso a partir do registro ao topo da pilha. O valor de $n_p$ - $n_a$ pode ser pré-computado em tempo de compilação

 \item<1-> Após seguir $n_p$ - $n_a$ elos, atingimos um registro ao qual a é local

  \end{itemize}
}


\subsection{Elos Entre Procedimentos e Procedimentos}

\frame
{
 \begin{itemize}

 \item<1-> Suponhamos que o procedimento p com profundidade de aninhamento $n_p$ chame o procedimento x à profundidade de aninhamento $n_x$. O código para estabelecer o elo de acesso no procedimento chamado depende desse último estar aninhado ou não no chamador.

 \item<1-> Caso $n_p \le n_x$. Uma vez que o procedimento chamado x está aninhado mais profundamente do que p, terá que estar declarrado dentro de p, ou não estaria acessível a p. Esse caso ocorre quando sort chama quicksort e quando quicksort chama partition. Nesse caso, o elo de acesso no procedimento de chamada terá de apontar para o elo de acesso no registro de ativação do chamador, exatamente abaixo da pilha. 
  \end{itemize}
}


\frame
{
 \begin{itemize}

 \item<1-> Caso $n_p \ge n_x$.

 \item<1-> Ocorre quando partition chama exchange

 \item<1-> Seguindo-se $n_p - n_x +1$ elos de acesso a partir do chamador atingimos o registro de ativação mais recente do procedimento que envolve estática e mais proximamente tanto o procedimento chamado quanto o chamador.

 \item<1->  O elo de acesso atingido, é aquele para o qual o elo de acesso no procedimento chamado precisarpa apontar. De novo, $n_p - n_x +1$ pode ser computado em tempo de compilação. 

  \end{itemize}
}


\frame
{
 \begin{figure}

 	\includegraphics[width=0.8\textwidth]{Imag3.jpg}
 	\label{Imag3}
 \end{figure}
}



\frame
{
\frametitle{Parêmtros do Tipo Procedimento}
 \begin{itemize}


 \item<1-> As regras do escopo léxico se aplicam mesmo quando um procedimento aninhado é passado como parâmetro

 \item<1-> Um procedimento aninhado, que seja passado como parâmetro, precisa carregar seu elo de acesso junto, como mostrado na próxima figura

 \item<1-> Quando o procedimento c passa para f , determina o elo de acesso para f, como faria se estivesse chamado f. Esse elo é passado junto com f para b. Subsequentemente, quando f for ativado a partir de b, o elo é usado para estabelecer o elo de acesso no registro de ativação para f

  \end{itemize}
}

\subsection{Displays}

\frame
{
 \begin{itemize}

 \item<1-> Um acesso aos nomes locais mais rápido que o proposto com elos de acesso pode ser atingido com o uso de um array de ponteiros para os registros de ativação denominado display

 \item<1-> O display é mantido na memória de tal forma que um não local de profundidade i estaria na posição de índice [i] no display

 \item<1-> Usar um display é geralmente mais rápido do que seguir elos de acesso, porque o registro de ativação que abriga um não local é encontrado através do acesso de um elemento do display, ao invés de seguir exatamente um apontador

  \end{itemize}
}

\frame
{

 \begin{figure}

 	\includegraphics[width=0.8\textwidth]{Imag4.jpg}
 	\label{Imag4}
 \end{figure}
}

\subsection{Escopo Dinâmico}

\frame
{

 \begin{figure}

 	\includegraphics[width=0.8\textwidth]{Imag5.jpg}
 	\label{Imag5}
 \end{figure}
}



\frame
{
 \begin{itemize}

 \item<1-> Sob o escopo dinâmico, uma nova ativação herda as amarrações existentes para os nomes não locais namemória. Um nome não local a, na ativação chamada, se refere à mesma memória que tinha associada quando na ativação que a chamou.

 \item<1-> Sob o escopo léxico de Pascal, o r não local está no escopo da declaração à linha 2, de forma que a saída do programa é

 \item<1-> 0.250	0.250

 \item<1-> 0.250	0.250
  \end{itemize}
}



\frame
{
 \begin{itemize}

 \item<1-> Entretanto sob o escopo dinâmico a saída é

 \item<1-> 0.250	0.125

 \item<1-> 0.250	0.125

 \item<1-> Quando show é chamado às linhas 10-11 do programa principal 0.250 é escrito porque a variável local ao programa principal r é usada. Entretanto, quando show é chamado à linha 7, de dentro de small, 0.125 é escrito, porque a variável r, local a small é usada.
  \end{itemize}
}


\subsection{Acesso Profundo}
\frame
{
 \begin{itemize}

 \item<1-> Dispensa elos de acesso e utiliza elos de controle para pesquisar na pilha

 \item<1-> Procuram pelo primeiro regristro de ativação que contenha a memória para o  nome não local

 \item<1-> A profundidade até a qual se procura depende da entrada

 \item<1-> Não pode ser determinada em tempo de compilação

  \end{itemize}
}




\frame
{
 \begin{itemize}

 \item<1-> Guarda o valor corrente de cada nome em memória estaticamente reservada

 \item<1-> O valor prévio dos nomes é salvo para cada procedimento que se inicia

 \item<1-> O nome precisa ser restaurado quando o procedimento acabar

  \end{itemize}
}



\section{Transmissão de Parâmetros}

\frame{
	$$a[i] := a[j]$$

	\begin{itemize}
		\item<1-> valor-l: posição de memória
		\item<1-> valor-r: valor contido na memória
	\end{itemize}
}

\subsection{Chamada por Valor}
\frame{
	\begin{itemize}
		\item<1-> Simples: usado em C e Pascal
		\item<1-> Memória é alocada para todos os parametros
		\item<1-> O valor-r do argumento é escrito nesses espaços de memória
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Não afetam os valores no escopo onde a função foi chamada
		\item<1-> Só pode alterar posições de memória se ponteiros forem passados.
	\end{itemize}
}

\subsection{Chamada por Referência}
\frame{
	\begin{itemize}
		\item<1-> Chamada por endereço ou chamada por localização
		\item<1-> Passa-se ponteiros para todos os argumentos (valores-l)
		\item<1-> Se o argumento não for um valor-l é alocado espaço para armazenar os dados
		\item<1-> Esse espaço tem que ser desalocado após conclusão da função		
	\end{itemize}
}

\subsection{Cópia-e-restauração}
\frame{
	\begin{itemize}
		\item<1-> Variação da chamada por referência
		\item<1-> Argumentos que são valores-l copiados para um novo espaço de memória e então passados por referência
		\item<1-> Após a função retornar os valores são copiados da memória recém alocadas
	\end{itemize}
}
\frame{
	\begin{itemize}
		\item<1-> Útil em ambientes multi-threaded
		\item<1-> Resultado indefinido se o mesmo parametro for passado multiplas vezes
	\end{itemize}
}

\subsection{Chamada por Nome}

\frame{
	\begin{itemize}
		\item<1-> Semelhante a uma macro: corpo da função é expandido no contexto da chamada, mantendo exatamente as variáveis passadas como parametro.
		\item<1-> Capture-avoiding substitution: nomes locais no procedimento são mantidos distintos do escopo onde o procedimento foi chamado (exceto pelos argumentos) e envolver parametros por parenteses.
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Aumenta o tamanho do arquivo
		\item<1-> Pode ser mais eficiente por reduzir overhead e acesso/cópia de argumentos não usados
		\item<1-> Pode ser menos eficiente por reduzir quantidade de acesso a argumentos
	\end{itemize}
}

\section{Tabela de símbolos}

\frame{
	\begin{itemize}
		\item<1-> Utilizada para controlar informações de escopo e amarrações de nomes
		\item<1-> Importante para linguagens com coletores de lixo
		\item<1-> Duas principais maneiras de implementar: listas ligadas e tabelas hash
		\item<1-> Duas medidas de tempo importantes: adicionar e localizar símbolos
	\end{itemize}
}

\subsection{Entradas na tabela de símbolos}
\frame{
	\begin{itemize}
		\item<1-> Cada entrada corresponde a um nome
		\item<1-> Não necessariamente uniformes
		\item<1-> Informações constantemente adicionadas
		\item<1-> Podem haver diferentes estruturas com o mesmo nome:
	\end{itemize}

	\begin{tabbing}
		int x;\\
		struct x {float y,z};
	\end{tabbing}
	
	Tanto to inteiro quanto a estrutura são registrados na tabela de símbolos.
}

\subsection{Caracteres num nome}
\frame{
	\begin{itemize}
		\item<1-> Para reduzir o tamanho da tabela de simbolos os lexemas dos identificadores podem ser substituidos por identificadores de tamanho fixo
		\item<1-> Caso os nomes não sejam mantidos recomenda-se o uso de ponteiros para os nomes (menos eficiente)
	\end{itemize}
}

\frame{
\begin{figure}[h]
 \centering
 \includegraphics[keepaspectratio=true,scale=0.7]{./caracteres.png}
 %\caption{}
\end{figure}

}

\subsection{Tratamento de escopo}
\frame{
	\begin{itemize}
		\item<1-> A tabela de simbolos sempre guarda um ponteiro para a próxima posição vazia
		\item<1-> Novos elementos são adicionados nessa posição
		\item<1-> Ao procurar um símbolo inicia-se do último até encontrar um com a correta função sintática e no escopo correto
		\item<1-> Se não encontrar o simbolo não foi previamente declarado
	\end{itemize}
}

\frame{
	\begin{itemize}
		\item<1-> Atribuição de numeros a cada procedimento
		\item<1-> Ao procurar um símbolo verifica-se sua visibilidade de acordo com o procedimento sendo executado
		\item<1-> No fim de um escopo as entradas criadas explicitamente para aquele escopo devem ser removidas ou desativadas
	\end{itemize}


	\begin{tabbing}
		int i = 1;\\
		for (int i=0; i==10; ++i)\{\\
		    print(i);\\
		\}\\
		print(i);
	\end{tabbing}
}

\subsection{Lista}
\frame{
	\begin{itemize}
		\item<1-> Mais fácil de implementar
		\item<1-> Ocupa menos memória
		\item<1-> Ineficiente para grande quantidade de símbolos
	\end{itemize}
}


\subsection{Tabela hash}
\frame{
	\begin{itemize}
		\item<1-> Mais complexo de implementar
		\item<1-> Ocupa mais memória
		\item<1-> Com uma boa escolha de função hash reduz drásticamente o tempo de pesquisa
		\item<1-> Cada bucket funciona como uma lista
	\end{itemize}
}

\section{}
\frame{
	Dúvidas?
}
\end{document}
